home *** CD-ROM | disk | FTP | other *** search
/ Shareware Super Platinum 8 / Shareware Super Platinum 8.iso / mac / WIN_PRO / DS-1.ZIP;1 / RUNTIME.ZIP / RSTRUCT.R < prev    next >
Encoding:
Text File  |  1992-02-10  |  13.8 KB  |  474 lines
  1. /*
  2.  * File: rstruct.r
  3.  *  Contents: addmem, cplist, cpset, hmake, hchain, hfirst, hnext, hgrow,
  4.  *  hshrink, memb
  5.  */
  6.  
  7. /*
  8.  * addmem - add a new set element block in the correct spot in
  9.  *  the bucket chain.
  10.  */
  11.  
  12. novalue addmem(ps,pe,pl)
  13. union block **pl;
  14. struct b_set *ps;
  15. struct b_selem *pe;
  16.    {
  17.    ps->size++;
  18.    if (*pl != NULL )
  19.       pe->clink = *pl;
  20.    *pl = (union block *) pe;
  21.    }
  22.  
  23. /*
  24.  * cplist(dp1,dp2,i,j) - copy sublist dp1[i:j] into dp2.
  25.  */
  26.  
  27. int cplist(dp1, dp2, i, j)
  28. dptr dp1, dp2;
  29. word i, j;
  30.    {
  31.    register dptr dp;
  32.    word size, nslots;
  33.    tended struct b_list *lp1, *lp2;
  34.    tended struct b_lelem *bp1, *bp2;
  35.  
  36.    /*
  37.     * Calculate the size of the sublist.
  38.     */
  39.    size = nslots = j - i;
  40.    if (nslots == 0)
  41.       nslots = MinListSlots;
  42.  
  43.    /*
  44.     * Get pointers to the list and list elements for the source list
  45.     *  (bp1, lp1) and the sublist (bp2, lp2).
  46.     */
  47.    lp1 = (struct b_list *) BlkLoc(*dp1);
  48.    bp1 = (struct b_lelem *) lp1->listhead;
  49.    Protect(lp2 = (struct b_list *) alclist(size), return Error);
  50.    Protect(bp2 = (struct b_lelem *)alclstb(nslots,(word)0,size), return Error);
  51.    lp2->listhead = lp2->listtail = (union block *) bp2;
  52.    dp = bp2->lslots;
  53.  
  54.    /*
  55.     * Locate the block containing element i in the source list.
  56.     */
  57.    if (size > 0) {
  58.       while (i > bp1->nused) {
  59.          i -= bp1->nused;
  60.          bp1 = (struct b_lelem *) bp1->listnext;
  61.          }
  62.       }
  63.  
  64.    /*
  65.     * Copy elements from the source list into the sublist, moving to
  66.     *  the next list block in the source list when all elements in a
  67.     *  block have been copied.
  68.     */
  69.    while (size > 0) {
  70.       j = bp1->first + i - 1;
  71.       if (j >= bp1->nslots)
  72.          j -= bp1->nslots;
  73.       *dp++ = bp1->lslots[j];
  74.       if (++i > bp1->nused) {
  75.          i = 1;
  76.          bp1 = (struct b_lelem *) bp1->listnext;
  77.          }
  78.       size--;
  79.       }
  80.  
  81.    /*
  82.     * Fix type and location fields for the new list.
  83.     */
  84.    dp2->dword = D_List;
  85.    BlkLoc(*dp2) = (union block *) lp2;
  86.    return Succeeded;
  87.    }
  88.  
  89. /*
  90.  * cpset(dp1,dp2,n) - copy set dp1 to dp2, reserving memory for n entries.
  91.  */
  92. int cpset(dp1, dp2, n)
  93. dptr dp1, dp2;
  94. word n;
  95.    {
  96.    union block *src;
  97.    tended union block *dst;
  98.    tended struct b_slots *seg;
  99.    tended struct b_selem *ep, *prev;
  100.    struct b_selem *se;
  101.    register word slotnum;
  102.    register int i;
  103.  
  104.    /*
  105.     * Make a new set organized like dp1, with room for n elements.
  106.     */
  107.    dst = hmake(T_Set, BlkLoc(*dp1)->set.mask + 1, n);
  108.    if (dst == NULL)
  109.       return Error;
  110.    /*
  111.     * Copy the header and slot blocks.
  112.     */
  113.    src = BlkLoc(*dp1);
  114.    dst->set.size = src->set.size;    /* actual set size */
  115.    dst->set.mask = src->set.mask;    /* hash mask */
  116.    for (i = 0; i < HSegs && src->set.hdir[i] != NULL; i++)
  117.       memcopy((char *)dst->set.hdir[i], (char *)src->set.hdir[i],
  118.          src->set.hdir[i]->blksize);
  119.    /*
  120.     * Work down the chain of element blocks in each bucket
  121.     *    and create identical chains in new set.
  122.     */
  123.    for (i = 0; i < HSegs && (seg = dst->set.hdir[i]) != NULL; i++)
  124.       for (slotnum = segsize[i] - 1; slotnum >= 0; slotnum--)  {
  125.      prev = NULL;
  126.          for (ep = (struct b_selem *)seg->hslots[slotnum];
  127.            ep != NULL; ep = (struct b_selem *)ep->clink) {
  128.             Protect(se = alcselem(&ep->setmem, ep->hashnum), return Error);
  129.         if (prev == NULL)
  130.         seg->hslots[slotnum] = (union block *)se;
  131.         else
  132.         prev->clink = (union block *)se;
  133.             se->clink = ep->clink;
  134.         prev = se;
  135.             }
  136.          }
  137.    dp2->dword = D_Set;
  138.    BlkLoc(*dp2) = dst;
  139.    if (TooSparse(dst))
  140.       hshrink(dst);
  141.    return Succeeded;
  142.    }
  143.  
  144. /*
  145.  * hmake - make a hash structure (Set or Table) with a given number of slots.
  146.  *  If *nslots* is zero, a value appropriate for *nelem* elements is chosen.
  147.  *  A return of NULL indicates allocation failure.
  148.  */
  149. union block *hmake(tcode, nslots, nelem)
  150. int tcode;
  151. word nslots, nelem;
  152.    {
  153.    word seg, t, blksize, elemsize;
  154.    tended union block *blk;
  155.    struct b_slots *segp;
  156.  
  157.    if (nslots == 0)
  158.       nslots = (nelem + MaxHLoad - 1) / MaxHLoad;
  159.    for (seg = t = 0; seg < (HSegs - 1) && (t += segsize[seg]) < nslots; seg++)
  160.       ;
  161.    nslots = ((word)HSlots) << seg;    /* ensure legal power of 2 */
  162.    if (tcode == T_Table) {
  163.       blksize = sizeof(struct b_table);
  164.       elemsize = sizeof(struct b_telem);
  165.       }
  166.    else {    /* T_Set */
  167.       blksize = sizeof(struct b_set);
  168.       elemsize = sizeof(struct b_selem);
  169.       }
  170.    if (!blkreserve((word)(blksize + (seg + 1) * sizeof(struct b_slots)
  171.       + (nslots - HSlots * (seg + 1)) * sizeof(union block *)
  172.       + nelem * elemsize))) return NULL;
  173.    Protect(blk = alchash(tcode), return NULL);
  174.    for (; seg >= 0; seg--) {
  175.       Protect(segp = alcsegment(segsize[seg]), return NULL);
  176.       blk->set.hdir[seg] = segp;
  177.       }
  178.    blk->set.mask = nslots - 1;
  179.    return blk;
  180.    }
  181.  
  182. /*
  183.  * hchain - return a pointer to the word that points to the head of the hash
  184.  *  chain for hash number hn in hashed structure s.
  185.  */
  186.  
  187. /*
  188.  * lookup table for log to base 2; must have powers of 2 through (HSegs-1)/2.
  189.  */
  190. static unsigned char log2h[] = {
  191.    0,1,2,2, 3,3,3,3, 4,4,4,4, 4,4,4,4, 5,5,5,5, 5,5,5,5, 5,5,5,5, 5,5,5,5,
  192.    };
  193.  
  194. union block **hchain(pb, hn)
  195. union block *pb;
  196. register uword hn;
  197.    {
  198.    register struct b_set *ps;
  199.    register word slotnum, segnum, segslot;
  200.  
  201.    ps = (struct b_set *)pb;
  202.    slotnum = hn & ps->mask;
  203.    if (slotnum >= HSlots * sizeof(log2h))
  204.       segnum = log2h[slotnum >> (LogHSlots + HSegs/2)] + HSegs/2;
  205.    else
  206.       segnum = log2h[slotnum >> LogHSlots];
  207.    segslot = hn & (segsize[segnum] - 1);
  208.    return &ps->hdir[segnum]->hslots[segslot];
  209.    }
  210.  
  211. /*
  212.  * hgfirst - initialize for generating set or table, and return first element.
  213.  */
  214.  
  215. union block *hgfirst(bp, s)
  216. union block *bp;
  217. struct hgstate *s;
  218.    {
  219.    int i;
  220.  
  221.    s->segnum = 0;                /* set initial state */
  222.    s->slotnum = -1;
  223.    s->tmask = bp->table.mask;
  224.    for (i = 0; i < HSegs; i++)
  225.       s->sghash[i] = s->sgmask[i] = 0;
  226.    return hgnext(bp, s, (union block *)0);    /* get and return first value */
  227.    }
  228.  
  229. /*
  230.  * hgnext - return the next element of a set or table generation sequence.
  231.  *
  232.  *  We carefully generate each element exactly once, even if the hash chains
  233.  *  are split between calls.  We do this by recording the state of things at
  234.  *  the time of the split and checking past history when starting to process
  235.  *  a new chain.
  236.  *
  237.  *  Elements inserted or deleted between calls may or may not be generated. 
  238.  *
  239.  *  We assume that no structure *shrinks* after its initial creation; they
  240.  *  can only *grow*.
  241.  */
  242.  
  243. union block *hgnext(bp, s, ep)
  244. union block *bp;
  245. struct hgstate *s;
  246. union block *ep;
  247.    {
  248.    int i;
  249.    word d, m;
  250.    uword hn;
  251.  
  252.    /*
  253.     * Check to see if the set or table's hash buckets were split (once or
  254.     *  more) since the last call.  We notice this unless the next entry
  255.     *  has same hash value as the current one, in which case we defer it
  256.     *  by doing nothing now.
  257.     */
  258.    if (bp->table.mask != s->tmask &&
  259.       (ep->telem.clink == NULL ||
  260.       ep->telem.clink->telem.hashnum != ep->telem.hashnum)) {
  261.       /*
  262.        * Yes, they did split.  Make a note of the current state.
  263.        */
  264.       hn = ep->telem.hashnum;
  265.       for (i = 1; i < HSegs; i++)
  266.          if ((((word)HSlots) << (i - 1)) > s->tmask) {
  267.         /*
  268.          * For the newly created segments only, save the mask and
  269.          *  hash number being processed at time of creation.
  270.          */
  271.         s->sgmask[i] = s->tmask;
  272.         s->sghash[i] = hn;
  273.          }
  274.       s->tmask = bp->table.mask;
  275.       /*
  276.        * Find the next element in our original segment by starting
  277.        *  from the beginning and skipping through the current hash
  278.        *  number.  We can't just follow the link from the current
  279.        *  element, because it may have moved to a new segment.
  280.        */
  281.       ep = bp->table.hdir[s->segnum]->hslots[s->slotnum];
  282.       while (ep != NULL && ep->telem.hashnum <= hn)
  283.          ep = ep->telem.clink;
  284.       }
  285.  
  286.    else {
  287.       /*
  288.        * There was no split, or else if there was we're between items
  289.        *  that have identical hash numbers.  Find the next element in
  290.        *  the current hash chain.
  291.        */
  292.       if (ep != NULL)            /* already NULL on very first call */
  293.          ep = ep->telem.clink;        /* next element in chain, if any */
  294.    }
  295.  
  296.    /*
  297.     * If we don't yet have an element, search successive slots.
  298.     */
  299.    while (ep == NULL) {
  300.       /*
  301.        * Move to the next slot and pick the first entry.
  302.        */
  303.       s->slotnum++;
  304.       if (s->slotnum >= segsize[s->segnum]) {
  305.      s->slotnum = 0;        /* need to move to next segment */
  306.      s->segnum++;
  307.      if (s->segnum >= HSegs || bp->table.hdir[s->segnum] == NULL)
  308.         return 0;            /* return NULL at end of set/table */
  309.          }
  310.       ep = bp->table.hdir[s->segnum]->hslots[s->slotnum];
  311.       /*
  312.        * Check to see if parts of this hash chain were already processed.
  313.        *  This could happen if the elements were in a different chain,
  314.        *  but a split occurred while we were suspended.
  315.        */
  316.       for (i = s->segnum; (m = s->sgmask[i]) != 0; i--) {
  317.          d = (word)(m & s->slotnum) - (word)(m & s->sghash[i]);
  318.          if (d < 0)            /* if all elements processed earlier */
  319.             ep = NULL;            /* skip this slot */
  320.          else if (d == 0) {
  321.             /*
  322.              * This chain was split from its parent while the parent was
  323.              *  being processed.  Skip past elements already processed.
  324.              */
  325.             while (ep != NULL && ep->telem.hashnum <= s->sghash[i])
  326.                ep = ep->telem.clink;
  327.             }
  328.          }
  329.       }
  330.  
  331.    /*
  332.     * Return the element.
  333.     */
  334.    return ep;
  335.    }
  336.  
  337. /*
  338.  * hgrow - split a hashed structure (doubling the buckets) for faster access.
  339.  */
  340.  
  341. novalue hgrow(bp)
  342. union block *bp;
  343.    {
  344.    register union block **tp0, **tp1, *ep;
  345.    register word newslots, slotnum, segnum;
  346.    tended struct b_set *ps;
  347.    struct b_slots *seg, *newseg;
  348.    union block **curslot;
  349.  
  350.    ps = (struct b_set *) bp;
  351.    if (ps->hdir[HSegs-1] != NULL)
  352.       return;                /* can't split further */
  353.    newslots = ps->mask + 1;
  354.    Protect(newseg = alcsegment(newslots), return);
  355.  
  356.    curslot = newseg->hslots;
  357.    for (segnum = 0; (seg = ps->hdir[segnum]) != NULL; segnum++)
  358.       for (slotnum = 0; slotnum < segsize[segnum]; slotnum++)  {
  359.          tp0 = &seg->hslots[slotnum];    /* ptr to tail of old slot */
  360.          tp1 = curslot++;        /* ptr to tail of new slot */
  361.          for (ep = *tp0; ep != NULL; ep = ep->selem.clink) {
  362.             if ((ep->selem.hashnum & newslots) == 0) {
  363.                *tp0 = ep;        /* element does not move */
  364.                tp0 = &ep->selem.clink;
  365.                }
  366.             else {
  367.                *tp1 = ep;        /* element moves to new slot */
  368.                tp1 = &ep->selem.clink;
  369.                }
  370.             }
  371.          *tp0 = *tp1 = NULL;
  372.          }
  373.    ps->hdir[segnum] = newseg;
  374.    ps->mask = (ps->mask << 1) | 1;
  375.    }
  376.  
  377. /*
  378.  * hshrink - combine buckets in a set or table that is too sparse.
  379.  *
  380.  *  Call this only for newly created structures.  Shrinking an active structure
  381.  *  can wreak havoc on suspended generators.
  382.  */
  383. novalue hshrink(bp)
  384. union block *bp;
  385.    {
  386.    register union block **tp, *ep0, *ep1;
  387.    int topseg, curseg;
  388.    word slotnum;
  389.    tended struct b_set *ps;
  390.    struct b_slots *seg;
  391.    union block **uppslot;
  392.  
  393.    ps = (struct b_set *)bp;
  394.    topseg = 0;
  395.    for (topseg = 1; topseg < HSegs && ps->hdir[topseg] != NULL; topseg++)
  396.       ;
  397.    topseg--;
  398.    while (TooSparse(ps)) {
  399.       uppslot = ps->hdir[topseg]->hslots;
  400.       ps->hdir[topseg--] = NULL;
  401.       for (curseg = 0; (seg = ps->hdir[curseg]) != NULL; curseg++)
  402.          for (slotnum = 0; slotnum < segsize[curseg]; slotnum++)  {
  403.             tp = &seg->hslots[slotnum];        /* tail pointer */
  404.             ep0 = seg->hslots[slotnum];        /* lower slot entry pointer */
  405.             ep1 = *uppslot++;            /* upper slot entry pointer */
  406.             while (ep0 != NULL && ep1 != NULL)
  407.                if (ep0->selem.hashnum < ep1->selem.hashnum) {
  408.                   *tp = ep0;
  409.                   tp = &ep0->selem.clink;
  410.                   ep0 = ep0->selem.clink;
  411.                   }
  412.                else {
  413.                   *tp = ep1;
  414.                   tp = &ep1->selem.clink;
  415.                   ep1 = ep1->selem.clink;
  416.                   }
  417.             while (ep0 != NULL) {
  418.                *tp = ep0;
  419.                tp = &ep0->selem.clink;
  420.                ep0 = ep0->selem.clink;
  421.                }
  422.             while (ep1 != NULL) {
  423.                *tp = ep1;
  424.                tp = &ep1->selem.clink;
  425.                ep1 = ep1->selem.clink;
  426.                }
  427.             }
  428.       ps->mask >>= 1;
  429.       }
  430.    }
  431.  
  432. /*
  433.  * memb - sets res flag to 1 if x is a member of a set or table, or to 0 if not.
  434.  *  Returns a pointer to the word which points to the element, or which
  435.  *  would point to it if it were there.
  436.  */
  437.  
  438. union block **memb(pb, x, hn, res)
  439. union block *pb;
  440. dptr x;
  441. register uword hn;
  442. int *res;                /* pointer to integer result flag */
  443.    {
  444.    struct b_set *ps;
  445.    register union block **lp;
  446.    register struct b_selem *pe;
  447.    register uword eh;
  448.  
  449.    ps = (struct b_set *)pb;
  450.    lp = hchain(pb, hn);
  451.    /*
  452.     * Look for x in the hash chain.
  453.     */
  454.    *res = 0;
  455.    while ((pe = (struct b_selem *)*lp) != NULL) {
  456.       eh = pe->hashnum;
  457.       if (eh > hn)            /* too far - it isn't there */
  458.          return lp;
  459.       else if ((eh == hn) && (equiv(&pe->setmem, x)))  {
  460.          *res = 1;
  461.          return lp;
  462.          }
  463.       /*
  464.        * We haven't reached the right hashnumber yet or
  465.        *  the element isn't the right one so keep looking.
  466.        */
  467.       lp = &(pe->clink);
  468.       }
  469.    /*
  470.     *  At end of chain - not there.
  471.     */
  472.    return lp;
  473.    }
  474.